Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Parameter study of sound propagation between city canyons with a coupled FDTD-PE model

A parameter study is performed for the case of two-dimensional sound propagation from a (source) city canyon to a nearby, identical (receiver) city canyon. Focus was on sound pressure levels, relative to the free field, in the shielded canyon. An accurate and efficient coupled FDTD-PE model was applied, exploiting symmetry of the source and receiver canyon. With the proposed calculation method, simulations were necessary in only half the sound propagation domain. The shielding in the receiver canyon in case of a coherent line source was compared to the shielding by an incoherent line source, by means of sound propagation calculations in a number of 2D cross-sections through source and receiver. It was found that the shielding is rather insensitive to the width-height ratio of the canyons. The presence of diffusely reflecting façades and balconies lead to an important increase in shielding compared to flat façades. Rigid façades yield significantly lower shielding compared to partly reflecting façades. Effects of a moving atmosphere were modeled in detail. Shielding decreases significantly in case of downwind sound propagation when comparing to sound propagation in a non-moving atmosphere. Refraction is the most important effect in the latter. In case of upwind sound propagation, turbulent scattering plays an important role and the shielding is similar to the one of a non-moving atmosphere for the parameters used in this paper. The combination of effects, as is shown by some examples, is in general not a simple addition of the separate effects.     

Algorithms for finding clique-transversals of graphs

A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. It is NP-hard to determine the minimum cardinality τ _c of a clique-transversal of G. In this work, first we propose an algorithm for determining this parameter for a general graph, which runs in polynomial time, for fixed τ _c . This algorithm is employed for finding the minimum cardinality clique-transversal of [`(3K₂)]\overline{3K_{2}} -free circular-arc graphs in O(n ⁴) time. Further we describe an algorithm for determining τ _c of a Helly circular-arc graph in O(n) time. This represents an improvement over an existing algorithm by Guruswami and Pandu Rangan which requires O(n ²) time. Finally, the last proposed algorithm is modified, so as to solve the weighted version of the corresponding problem, in O(n ²) time.     

Algorithms for clique-independent sets on subclasses of circular-arc graphs

A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n²). These algorithms suppose that an HCA model of the graph is given.     

Obstructions to chordal circular-arc graphs of small independence number

A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining two vertices of the quadruple, or are connected by some path missed by the remaining two vertices. This is akin to the notion of asteroidal triple used in the classical characterization of interval graphs by Lekkerkerker and Boland [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.].In this note, we first observe that blocking quadruples are obstructions for circular-arc graphs. We then focus on chordal graphs, and study the relationship between the structure of chordal graphs and the presence/absence of blocking quadruples.Our contribution is two-fold. Firstly, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples. In particular, we observe that all the forbidden subgraphs are variants of the subgraphs forbidden for interval graphs [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.]. Secondly, we show that the absence of blocking quadruples is sufficient to guarantee that a chordal graph with no independent set of size five is a circular-arc graph. In our proof we use a novel geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree.     

Technical challenges in tackling regulatory concerns for urban atmospheric nanoparticles

Recent Euro 5 and Euro 6 vehicle emission standards are the first ever initiative to control particles on a number basis at the source. Related standards are also desirable for ambient nanoparticles (taken in this article to be those below 300 nm) to protect against possible adverse effects on public health and the environment. However, there are a number of technical challenges that need to be tackled before developing a regulatory framework for atmospheric nanoparticles. Some of the challenges derive from a lack of standardisation of the key measurement parameters, including sampling, necessary for robust evaluation of particle number concentrations, especially in the context of insufficient knowledge of the physicochemical characteristics of emerging sources (i.e. bio-fuel derived and manufactured nanoparticles). Ideally, ambient concentrations of primary particles could be linked to primary particle emissions by use of nanoparticle dispersion models, and secondary nanoparticles using photochemical modeling tools. The limitations in these areas are discussed. Although there is inadequate information on the exact biological mechanism through which these particles cause harm, it is argued that this should not in itself delay the introduction of regulation. This article reviews the missing links between the existing knowledge of nanoparticle number concentrations and the advances required to tackle the technical challenges implied in developing regulations.     

多水平成层的非均匀介质圆弧形峡谷地下多点地震动模拟

开发了考虑圆弧场地水平多分层效应的地下多点地震动模拟可视化程序,验证其可靠性。首先,描述了给出的圆弧场地多分层效应的SH波动散射频域解,其本质是突破了传统均匀介质和分层不穿越峡谷前提的局限性;其次,利用从水平地表到峡谷表面再到地下土层的传递函数,通过两次传递得到了圆弧峡谷地下的目标功率谱和反应谱;进而,具体描述所导出的圆弧场地平-凹相关性的相干函数及其推导过程;最后,基于上述理论,开发了多层状的非均匀圆弧场地的多点地震动模拟程序,给出了模拟结果与目标功率谱、反应谱和相干函数的拟合对比,验证了该理论和程序的合理性和可靠性,便于所发展理论和方法的实用化和推广。     

圆弧形沉积场地对平面瑞利波散射的解析分析

分别采用Biot饱和多孔介质动力学理论和单相介质弹性动力学理论模拟层状沉积谷场地和 周围场地，利用波函数展开法，得出了层状饱和沉积场地对Rayleigh波散射的解析解．进 行参量分析，研究了无量纲入射波频率、层状沉积层排列顺序及相对刚度和厚度等因素对 Rayleigh波散射效应的影响.     

圆弧形凹陷地形表面覆盖层对入射平面P波的影响

利用Fourier-Bessel级数展开法给出了表面具有覆盖层的圆弧形凹陷地形对入射平面P波散射问题的一个解析解，并利用该解分析了不同形状凹陷地形表面覆盖层刚度和厚度对入射P波的影响。结果表明，凹陷地形表面覆盖层的存在，即使厚度很薄，对入射P波的散射也具有很大覆盖，覆盖层刚度和厚度的变化可显著改善凹陷地形场地的动力特性。